AI Basics: The Missionaries and Cannibals Problem

[baoshi.rao]

AI (Artificial Intelligence) is a concept that elevates sophistication, and true AI is far from just talk. Using a classic AI algorithm problem as an example, the author explains the problem-solving logic and methods, demonstrating the formation process of algorithms.

AI (Artificial Intelligence) is undoubtedly a buzzword these days. Much like the internet concept in the past, any project that associates itself with AI instantly appears cutting-edge and sophisticated.

AI is a vast field, a discipline encompassing a wide range of knowledge. Just thinking about AI applications, we can list several off the top of our heads, such as NLP (Natural Language Processing), TTS (Text-to-Speech), human-machine dialogue, speech synthesis, as well as the facial recognition we use daily, the emerging face-payment systems, smart cleaning robots at home, context-aware smart furniture, and intelligent finance.

Ubiquitous AI technology is closely intertwined with our lives and continuously influences them.

The concept of AI itself is sound, much like blockchain—it's a great idea. However, due to excessive speculation by some, the field has become uneven and mixed with subpar implementations.

In reality, we see situations where anyone who can write a few lines of logic dares to call themselves an AI engineer or an algorithm engineer. Projects with minimal logical judgments are branded as AI projects.

The current state is rather浮躁, lacking basic respect for science.

Most of the so-called AI projects we encounter today are merely integrations or repackaging of existing AI services available on the market. But to develop a core product, there's a long road ahead, requiring significant investments in manpower, resources, and finances.

Imagine all the services you provide are sourced from other manufacturers, with no proprietary technology of your own—this makes you highly susceptible to control by other vendors, unless your product gets acquired by a major player.

That said, products without core competitiveness, merely integrating others' functionalities, lack technical barriers and are easily imitated or surpassed, let alone building a moat.

Thus, in my opinion, the foundation of AI lies in algorithms—the most fundamental research involving extensive knowledge across computer science, psychology, operations research, and other disciplines.

Take text-to-speech as an example. Converting a single word to speech isn't hard, but transforming a long passage into fluent speech with customizable voice tones involves a seemingly small feature backed by massive R&D efforts.

The core of AI is algorithms. Different algorithms combine like DNA strands to form AI applications. Today, we'll start with the simplest example to embark on the journey of AI's most fundamental algorithms.

This problem is indeed basic—a quick online search yields numerous articles on it. I've read some myself but found many lacking rigor, with flawed code.

In this world, criticizing others is easiest, while self-awareness is hardest. Rather than complaining, I decided to write a better article to share with everyone.

Now, let's dive into the topic.

Three missionaries and three cannibals need to cross a river. There's only one boat, no boatman, and all six can row. However, the boat can carry only two people at a time. In any scenario where cannibals outnumber missionaries, the missionaries will be eaten. In other words, on either bank of the river, the number of cannibals must never exceed the number of missionaries.

How can all six cross safely without any missionaries being eaten?

Logically, this involves exploring various solutions until a viable one is found.

Initial state: All are on the left bank, aiming to reach the right bank:

Missionary1 Missionary2 Missionary3 ||River||
Cannibal1 Cannibal2 Cannibal3 ||River||

Step 1: Two cannibals cross to the right bank; one returns:

Missionary1 Missionary2 Missionary3 ||River||
Cannibal2 Cannibal3 ||River|| Cannibal1

Step 2: Two cannibals cross to the right bank; one returns:

Missionary1 Missionary2 Missionary3 ||River||
Cannibal3 ||River|| Cannibal1 Cannibal2

Step 3: Two missionaries cross; one missionary and one cannibal return:

Missionary2 Missionary3 ||River|| Missionary1
Cannibal2 Cannibal3 ||River|| Cannibal1

Step 4: Two missionaries cross; one cannibal returns:

||River|| Missionary1 Missionary2 Missionary3
Cannibal1 Cannibal2 Cannibal3 ||River||

Step 5: Two cannibals cross; one returns:

||River|| Missionary1 Missionary2 Missionary3
Cannibal2 Cannibal3 ||River|| Cannibal1

Step 6: Two cannibals cross:

||River|| Missionary1 Missionary2 Missionary3
||River|| Cannibal1 Cannibal2 Cannibal3

This problem can be understood as a decision-making issue, a classic foundational problem in AI.

While our analysis and solution seem to resolve the problem, a question arises: Are there other methods besides the one above? Which is the fastest? With only six people, manual analysis suffices. But what about 60 or 600 people? Relying on manual calculations becomes impractical. The solution lies in developing a search algorithm for computational assistance.

Analyzing initial and final states: The initial state is [3, 3, 1] (3 missionaries, 3 cannibals, boat on left), and the final state is [0, 0, 0].

From a state perspective, there are 32 possible states, derived from permutations of missionaries (0-3), cannibals (0-3), and boat location (0 or 1). Invalid states (where cannibals outnumber missionaries) are filtered out.

A state-space graph reveals all paths from initial to final states, representing safe crossing solutions.

Algorithmically, this involves graph traversal—depth-first or breadth-first search. For optimal solutions, shortest-path algorithms like Dijkstra's may apply.

The implementation approach is as follows:

Determine the passenger state on the boat. For example, the boat can carry 1 missionary and 1 cannibal, 2 missionaries, or 2 cannibals. The number of passengers is constrained by the boat's capacity, which in this problem is limited to a maximum of 2.

Based on the number of people transported by the boat and the requirements of the problem, we search for feasible transportation solutions and store them in a dynamic array.

To avoid redundant calculations, we also check whether the generated method already exists in the historical results. The historical results are also stored in a dynamic array. If a solution already exists in the history, we skip it and continue searching for new methods until all possible solutions are found.

The implemented algorithm, as shown in Figure 3-1, has been experimentally verified and ensures correct execution.


The execution results of the code reveal several safe river crossing methods, as illustrated in Figure 3-2.


In this article, we start with the classic problem of missionaries and cannibals crossing the river, analyze it in depth, and explain the fundamental logic and solutions for such problems. We also extend the algorithm for missionaries and cannibals.

Even after modifying parameters such as the number of missionaries, cannibals, and the boat's capacity, the algorithm can still perform calculations as required, demonstrating strong flexibility. See Figure 4-1 for the results after parameter adjustments.


However, this article has its limitations, as the algorithm still has room for optimization.

According to calculations, when the boat's maximum capacity is 2 and there are 8 missionaries and 8 cannibals, the program requires approximately 400,000 executions to find the first solution, as shown in Figure 4-2. The algorithm's time and space complexity remain high, indicating further optimization potential.


From this experiment, we can observe that even such a seemingly simple problem involves a significant amount of theoretical knowledge, including data structures, algorithms, and numerical computation. Moreover, the solution is not yet perfect and falls short of an ideal, elegant algorithm.

Tackling even this small problem to its algorithmic limits requires considerable effort. This is just a very basic and minor concept in artificial intelligence. Achieving true mastery is no easy feat, even for a Ph.D.

Thus, it's puzzling how some individuals with only one or two years of undergraduate education dare to call themselves algorithm engineers. It's unclear where such confidence comes from.

Genuine scientific research is tedious, requiring dedication, patience, and perseverance. Superficial performances may shine briefly, but only sincerity and diligence can ensure lasting success.

Finally, we hope this article proves helpful to readers.

Let’s strive together!